package analyze.one.topn;

/**
 * 在一堆数中找出前N个最大的数,采用二叉堆<br />
 * 
 * 此为最小二叉堆，即最顶层的元素最小，当超过size的数大于最小元素时，需要重排。也就是说，这里的最小堆算法是获取前size个最大的元素<br />
 * 
 * 同理，获取前n个最小的数据，那么就是最大二叉堆，堆顶是最大的元素
 * 
 * 模仿Lucene中的获得评分前N的DocumentID
 * 
 * @author Administrator
 *
 */
public class TopNCreator {
	private ITopNBean[] heap; // 存储数据
	private int size; // 已存数据个数,也代表指针位置
	private int maxSize; // 取前maxSize大的数
	private ITopNBean nullBean = new NullBean(-1);

	public TopNCreator(int maxSize) {
		super();
		this.maxSize = maxSize;
		heap = new ITopNBean[maxSize + 1];
		size = 0;
	}

	/**
	 * 插入数据
	 * 
	 * @param element
	 * @return
	 */
	public boolean insert(ITopNBean element) {
		// 未达到指定数据数量
		if (size < maxSize) {
			put(element);
			return true;
		} else if (size > 0 && element.value() > top().value()) { // 新数据大于最小的元素才进入,并调整数据顺序
			heap[1] = element; // 替换头部元素(也就是最小的元素)为当前元素(因为当前元素比头部元素大)
			adjustTop(); // 调整头部元素
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 存入数据
	 * 
	 * @param element
	 */
	public void put(ITopNBean element) {
		size++;
		heap[size] = element;
		upheap();
	}

	/**
	 * 返回top 最小数据保存在根节点
	 * 
	 * @return
	 */
	public ITopNBean top() {
		if (size > 0) {
			return heap[1];
		} else {
			return nullBean;
		}
	}

	public int getSize() {
		return size;
	}

	public void setSize(int size) {
		this.size = size;
	}

	// 节点升顶
	public final void upheap() {
		int i = size;// 失位节点的原始位置 i，它最终的正确位置依旧用i标记
		ITopNBean node = heap[i]; // 将失位节点保持在node变量上；node的最终正确位置，依旧用i标记
		int j = i >>> 1; // i 父节点位置 j，通过移位操作

		// 有父节点,并且失位节点node小于父节点,则要交换位置
		while (j > 0 && node.value() < heap[j].value()) {
			// 父节点与失位节点交换位置，其实只要将父节点放置在i位置上即可
			// 因为此时的j可能并不是node的最终位置
			heap[i] = heap[j];
			i = j; // 此时的i设置为父节点j，这是失位节点可能正确的位置
			j = i >>> 1; // 重新计算i的父节点，依旧记为j
		}
		heap[i] = node; // 将失位节点放入合适位置
	}

	/**
	 * 排放数据,从最小的元素开始排放,会删除该元素
	 * 
	 * @return
	 */
	public ITopNBean pop() {
		if (size > 0) {
			ITopNBean result = heap[1]; // 第一个元素（堆顶）作为结果返回，因为第一个元素最小
			heap[1] = heap[size]; // 堆尾元素放置到堆顶
			heap[size] = new NullBean(-1); // 最大的元素清空
			size--; // 指针前移
			downHeap(); // 堆顶沉降
			return result;
		} else {
			return nullBean;
		}
	}

	public final void adjustTop() {
		downHeap();
	}

	/**
	 * 节点沉降 往下沉降，替换了头部的数据后需要根据二叉堆的规则重排数据 保证根数据是最小的数据
	 */
	public void downHeap() {
		int i = 1;
		/*
		 * 刚插入的数据，分别和它的两个子元素比较
		 */
		ITopNBean node = heap[i]; // node表示失位节点，i是它初始的位置
		int j = i << 1; // 子元素a
		int k = j + 1; // 子元素b

		// 存在子元素b
		// 这一步的目的是找出两个子元素中较小的一个，用它来跟node进行比较
		// 因为能够与父节点交换的一定比父节点小且较小的子节点
		if (k <= size && heap[k].value() < heap[j].value()) {
			// 用j来标记最终与node比较的节点
			j = k;
		}

		// 一直循环，直到超出size(也就是数组大小)并且小于要插入的节点
		// 将node与j节点进行比较
		while (j <= size && heap[j].value() < node.value()) {
			// 如果j节点小于node，则表示j节点需要和i节点进行交换
			// 同样的，只要将j节点放置到i节点，此时的j可能是node的最终位置
			heap[i] = heap[j]; // 置换
			i = j; // i变为j
			j = i << 1; // j重新计算，变为i的父节点
			k = j + 1; // 另一个父节点

			// 存在子元素b
			// 这一步的目的是找出两个子元素中较小的一个，用它来跟node进行比较
			// 因为能够与父节点交换的一定比父节点小且较小的子节点
			if (k <= size && heap[k].value() < heap[j].value()) {
				// 用j来标记最终与node比较的节点
				j = k;
			}
		}
		heap[i] = node; // 将node节点放置到i位置上

	}

	public void print() {
		for (int i = 1; i <= maxSize; i++) {
			System.out.println(heap[i]);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TopNCreator find = new TopNCreator(5);
		int[] source = { 44, 65, 23, 45, 55, 78, 21, 32, 43, 876, 1, 66, 13,
				35, 38, 96, 437, 55, 980, 21, 1010, 1001, 1334, 42, 2354, 7788,
				344, 333, 557, 5454, 7664, 1235 };
		int maxNum = 10;
		long b = System.currentTimeMillis();
		maxNum = source.length;
		for (int i = 0; i < maxNum; i++) {
			// int a=(int)(Math.random()*maxNum);
			int a = source[i];
			find.insert(new IntegerBean(a));
			// System.out.println(find.insert(a)+":"+a);
		}

		System.out.println("================================");
		/* find.print(); */
		int max = find.getSize();
		for (int i = 0; i < max; i++) {
			System.out.println(find.pop());
		}
		System.out.println("cost : " + (System.currentTimeMillis() - b));
	}

	public ITopNBean[] getHeap() {
		return heap;
	}

	public void setHeap(ITopNBean[] heap) {
		this.heap = heap;
	}

	public int getMaxSize() {
		return maxSize;
	}

	public void setMaxSize(int maxSize) {
		this.maxSize = maxSize;
	}

}